package dp;

/**
 * 最长连续递增子数组，用动态规划求解
 * R[i]表示以i号元素结尾的连续递增子数组最大长度，易知递推公式为：
 * 1）R[i]=1; 若i=0
 * 2）R[i]=R[i-1]+1;若A[i]>=A[i-1];
 * 3）R[i]=1; 若A[i]<A[i-1];
 *
 * @author zj
 */
public class LongestContinuousAscSubArray {

    public static void main(String args[]) {
        int A[] = {1, 2, 3, 2, 1, 4};
        System.out.println(solution(A));
    }

    /**
     * @param arr
     */
    public static int solution(int arr[]) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int tmp[] = new int[arr.length];
        tmp[0] = 1;  //边界条件，以第一个元素结尾的最长递增子序列就是该元素本身，必然为1
        int max = tmp[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < arr[i - 1]) {
                tmp[i] = 1;
            } else {
                tmp[i] = tmp[i - 1] + 1;
            }
            max = tmp[i] > max ? tmp[i] : max;
        }
        for (int i = 0; i < tmp.length; i++) {
            System.out.print(tmp[i] + " ");
        }
        System.out.println();
        return max;
    }
}
